#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 链表排序

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// 链表排序
class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *newHead = new ListNode(-1);
        newHead->next = head;
        ListNode *cur = head->next, *lastSorted = head;
        while (cur)
        {
            if (lastSorted->val <= cur->val)
            {
                lastSorted = lastSorted->next;
            }
            else
            {
                ListNode *prev = newHead;
                while (prev->next->val <= cur->val)
                {
                    prev = prev->next;
                }
                lastSorted->next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
            }
            cur = lastSorted->next;
        }

        ListNode *sortedHead = newHead->next;
        delete newHead;
        return sortedHead;
    }
};

#include <iostream>
#include <vector>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *CreateList(const std::vector<int> &nums)
{
    ListNode *head = nullptr, *tail = head;
    for (auto x : nums)
    {
        ListNode *node = new ListNode(x);
        if (head == nullptr)
        {
            head = tail = node;
        }
        else
        {
            tail->next = node;
            // tail = tail->next;
            tail = node;
        }
    }

    return head;
}

ListNode *InsertBack(ListNode *head)
{
    ListNode *newHead = new ListNode(-1);
    ListNode *tail = newHead;
    ListNode *cur = head;
    while (cur)
    {
        ListNode *next = cur->next;
        tail->next = cur;
        // tail = tail->next;
        tail = cur;
        cur = next;
    }
    return newHead->next;
}

ListNode *InsertFront(ListNode *head)
{
    ListNode *cur = head, *newhead = nullptr;
    while (cur)
    {
        ListNode *next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

int main()
{
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    ListNode *head = CreateList(nums);
    ListNode *cur = head;
    while (cur)
    {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;

    cur = InsertBack(head);
    while (cur)
    {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;

    cur = InsertFront(head);
    while (cur)
    {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
    return 0;
}

// struct ListNode
// {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        // 1. 先求出需要逆序多少组
        int n = 0;
        ListNode *cur = head;
        while (cur)
        {
            n++;
            cur = cur->next;
        }

        n /= k;

        // 2. 重复 n 次：⻓度为 k 的链表的逆序即可
        ListNode *newhead = new ListNode(0);
        ListNode *tail = newhead;
        cur = head;
        for (int i = 0; i < n; i++)
        {
            ListNode *tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode *next = cur->next;
                cur->next = tail->next;
                tail->next = cur;
                cur = next;
            }
            tail = tmp;
        }

        // 把不需要翻转的接上
        tail->next = cur;
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};


